package com.hackerank.arrays;

/**
 * Minimum Swaps 最少交换次数
 * https://www.hackerrank.com/challenges/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays
 *
 * 题目大意：
 * 1、有个由连续整数（取值范围∈[1,2,3,4,......N]）组成的无序数组，你每次可以交换数组中任意两个元素，试求出最少进行多少次交换，
 *      可以让数组里的数值升序排序
 * 2、输入数字 n 代表数组的长度
 * 3、在下一行输入 n 个被空格隔开的 数字，表示数组中的元素
 * 4、输出最少经过多少次交换可以使数组元素保持升序 q
 *  * 5、如数组 [7,1,3,2,4,5,6]经过5步的交换过程如下：
 *  * i   arr                         swap (indices)
 *  * 0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
 *  * 1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
 *  * 2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
 *  * 3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
 *  * 4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
 *  * 5   [1, 2, 3, 4, 5, 6, 7]
 *  *
 * 解题思路：
 *
 * 1、循环节概念：一个数占据了另外一个数的位置，则将该数交换到正确的位置，
 *               那被交换的数可能不在正确位置则继续交换，直到按照该交换方式
 *               无法交换位置，所有被交换的数形成一个循环。
 * 2、任意交换位置的次数为： 数组长度N - 循环节个数
 * 3、解释：
 *          1）假设所有的数都有序，不用交换，则可视为每个数为一个元素个数只有1的循环节，即只能和自己交换，数组长度N - 循环节个数N，
 *          就表示了有序数组的最少交换次数
 *          2）假设数组是局部有序，有序个数为 K 则只需要在无序的元素中进行交换，可以先用数组N减去单个循环节K，即需要在N - K 个元素
 *          的数组中进行交换
 *          3）那无序的元素数组和循环节的关系如何推导呢？
 *          4）可理解为在一个循环节内，元素是混乱的，不影响循环节外的元素，就像排队只需要看谁占了自己位置，不用关心其他人
 *          5）这样一个长度为 X 的循环节，可推导出需要进行 X - 1 次交换（类似冒泡排序，只是不按索引冒泡）
 *          6）那也就是长度为 N 的数组 交换次数可推导出 N - K - K2，K2表示无序元素形成的循环节个数
 *          7）那 K 视为有效元素的单一元素循环节，则可抽象为 N - K（循环节个数）
 * 4、求解循环节的方法：
 *      1）遍历数组中的元素，如果该元素被访问过了，说明该元素已经在一个循环节当中，则继续循环下一个元素
 *      2）如果该元素没有被访问过，则可视为该元素为循环节一个起点，继续访问该元素值对应位置的元素，直到遍历回到该起点元素形成
 *          一个循环节，循环节个数加 1
 *      3）可证明以任意元素为起点进行步骤2的遍历一定能形成回到该起点循环节
 *
 * */
public class MinimumSwaps2 {
    static int minimumSwaps(int[] arr) {
        boolean[] flag = new boolean[arr.length];
        int count = 0;
        for(int i=0;i<arr.length;i++){
            if(flag[i]){
                continue;
            }else{
                int j = i;
                while(!flag[j]){
                    flag[j] = true;
                    j = arr[j] - 1;
                }
                count ++;
            }
        }
        return arr.length - count;
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 2, 4, 5, 6};
        int swap = minimumSwaps(arr);
        System.out.println(swap);
    }
}
